//给定 n 个整数，找出平均数最大且长度为 k 的连续子数组，并输出该最大平均数。 
//
// 
//
// 示例： 
//
// 
//输入：[1,12,-5,-6,50,3], k = 4
//输出：12.75
//解释：最大平均数 (12-5-6+50)/4 = 51/4 = 12.75
// 
//
// 
//
// 提示： 
//
// 
// 1 <= k <= n <= 30,000。 
// 所给数据范围 [-10,000，10,000]。 
// 
// Related Topics 数组 
// 👍 146 👎 0
#include <iostream>
#include <vector>
#include <set>
#include <numeric>

using namespace std;


//leetcode submit region begin(Prohibit modification and deletion)
class Solution {
public:
    double findMax(int start, vector<int>& nums,int k){
        double res = 0;
        if (start < nums.size()){
            for (int i = start; i < start + k; ++i) {
                res += nums[i];
            }
        }
        return res/k;
    }
    double findMaxAverage(vector<int>& nums, int k) {
        if (nums.empty())
            return 0;

        double res = -99999;
        for (int i = 0; i <= nums.size() - k; ++i) {
            if (findMax(i,nums,k) > res){
                res = findMax(i,nums,k);
            }
        }
        return res;
    }

    double findMaxAverage02(vector<int>& nums, int k) {
        int left = 0,right = 0;
        double res = -99999;
        while (right < nums.size()){
            if (right - left == k){
                if (accumulate(nums.begin()+left,nums.begin()+right,0) > res)
                    res = accumulate(nums.begin()+left,nums.begin()+right,0);
                left = right;
                right++;
            } else{
                right++;
            }
        }
        return res;
    }

    double findMaxAverage03(vector<int>& nums, int k){
        double sum = 0;
        for (int i = 0; i < k; ++i) {
            sum += nums[i];
        }
        double maxN = sum;
        for (int i = k; i < nums.size(); ++i) {
            sum = sum - nums[i-k] + nums[i];
            maxN = max(maxN,sum);
        }
        return maxN/k;
    }

};
//leetcode submit region end(Prohibit modification and deletion)
